/*
 * KMP模式匹配
 *
 * https://blog.csdn.net/v_july_v/article/details/7041827
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
 * 计算子串T的next数组
 *
 * next数值有两种形式
 * (1) 模式串下标从1开始
 * 例子：
 * +---------+---+---+---+---+---+---+
 * |    j    | 1 | 2 | 3 | 4 | 5 | 6 |
 * +---------+---+---+---+---+---+---+
 * | 模式串T | a | b | c | a | b | x |
 * +---------+---+---+---+---+---+---+
 * | next[j] | 0 | 1 | 1 | 1 | 2 | 3 |
 * +---------+---+---+---+---+---+---+
 *
 * next[j]的取值如下：
 * 1) 当 j = 1 时，值为 0；
 * 2) 对于 1 < k < j，存在 P1 P2 ... P(k-1) = P(j-k+1) ... P(j-1)，值为 k 的
      最大值 (即求子串的前缀后缀相同字符的最大长度k)；
 * 3) 其他情况，值为 1；
 *
 * 推导过程：
 * 当j=1时，next[1] = 0;
 * 当j=2时，j由1到j-1只有字符'a'，属于其它情况 next[2] = 1;
 * 当j=3时，j由1到j-1串是"ab"，显然"a"和"b"不相等，属于其它情况 next[3] = 1;
 * 当j=4时，j由1到j-1串是"abc"，显然"a"和"c"不相等，"ab"和"bc"不相等，
 *          属于其它情况 next[4] = 1;
 * 当j=5时，j由1到j-1串是"abca"，前缀字符"a"和后缀字符"a"相等，"ab"和"ca"不相等，
 *          "abc"和"bca"不相等，所以k值为2，next[5] = 2;
 * 当j=6时，j由1到j-1串是"abcab"，前缀字符"a"和后缀字符"b"不相等，
 *          前缀字符"ab"和后缀字符"ab"相等，"abc"和"cab"不相等，
 *          "abca"和"bcac"不相等，所以k值为3，next[6] = 3;
 *
 * 简单的推导方法: 第1位和第2位填固定值分别为0和1，从第三位开始(即n=3,4,5,...)，
 * 看前面n-1个字符，如果前后缀有m个字符相等(即前缀后缀相同字符的长度)，
 * 则next[j]=m+1，否则next[j]=1。
 *
 *
 * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 *
 *
 * (2) 模式串下标从0开始
 * 例子：
 * +---------+----+---+---+---+---+---+
 * |    j    | 0  | 1 | 2 | 3 | 4 | 5 |
 * +---------+----+---+---+---+---+---+
 * | 模式串T | a  | b | c | a | b | x |
 * +---------+----+---+---+---+---+---+
 * | next[j] | -1 | 0 | 0 | 0 | 1 | 2 |
 * +---------+----+---+---+---+---+---+
 *
 * 过程:
 * 1) 先求模式串前缀后缀的最大公共元素长度
 * +----------+---+---+---+---+---+---+
 * | 模式串T  | a | b | c | a | b | x |
 * +----------+---+---+---+---+---+---+
 * | 最大长度 | 0 | 0 | 0 | 1 | 2 | 0 |
 * +----------+---+---+---+---+---+---+
 *
 * 2) 求next数组，将步骤1求得的值整体右移一位，然后初值赋为-1
 * +---------+----+---+---+---+---+---+
 * |    j    | 0  | 1 | 2 | 3 | 4 | 5 |
 * +---------+----+---+---+---+---+---+
 * | 模式串T | a  | b | c | a | b | x |
 * +---------+----+---+---+---+---+---+
 * | next[j] | -1 | 0 | 0 | 0 | 1 | 2 |
 * +---------+----+---+---+---+---+---+
 *
 * 对abcab来说，第5个字符b之前的字符串abca中有长度为1的相同前缀后缀a，所以第5个
 * 字符b所对应的next值为1。
 *
 *
 * next 数组告诉我们：当模式串中的某个字符跟文本串中的某个字符匹配失配时，
 * 模式串下一步应该跳到哪个位置。如模式串中在j 处的字符跟文本串在i 处的字符
 * 匹配失配时，下一步用next [j] 处的字符继续跟文本串i 处的字符匹配，相当于
 * 模式串向右移动 j - next[j] 位。
 *
 *
 *
 * next数组解释:
 *
 * 主串    "bbc abcab zyacccabcabxxxaa"
 * 模式串  "abcabx"
 *
 * 过程:
 * 1)
 *   主串    bbc abcab zyacccabcabxxxaa
 *   模式串      abcabx
 *
 *   当模式串abcabx的最后一个字符x根主串的空格匹配失败时，模式串需要向右移动，
 *   但向右移动多少位呢？此时可以根据已经匹配的字符数为5个(abcab)，然后根据
 *   最大公共元素长度表可得失配字符x的上一位字符b对应的长度值为2，
 *   根据之前的结论，需要向右移动 j-next[j] = 5-2 = 3 位。
 *
 *   主串    bbc abcab zyacccabcabxxxaa
 *   模式串         abcabx
 *
 * 2)
 *   模式串向右移动3位后，发现c处再度失配，此时已经匹配了2个字符ab，c的上一位
 *   字符b所对应的最大公共元素长度为0，所以向右移动 2-0 = 2 位。
 *
 *   主串    bbc abcab zyacccabcabxxxaa
 *   模式串           abcabx
 *
 *
 * 通过上述匹配过程可以看出，问题的关键就是寻找模式串中最大长度的相同前缀和后缀，
 * 找到了模式串中每个字符之前的前缀和后缀公共部分的最大长度后，便可基于此匹配。
 * 而这个最大长度便正是next 数组要表达的含义。
 *
 * 当失配时，模式串向右移动的位数为:
 *    已匹配字符数 - 失配字符的上一位字符所对应的最大长度值
 *
 * 我们发现，当匹配到一个字符失配时，其实没必要考虑当前失配的字符，
 * 更何况我们每次失配时，都是看的失配字符的上一位字符对应的最大长度值。
 * 如此，便引出了next 数组。
 *
 * 把next 数组跟之前求得的最大长度表对比后，不难发现，next 数组相当于
 * "最大长度值" 整体向右移动一位，然后初始值赋为-1。意识到了这一点，
 * 你会惊呼原来next 数组的求解竟然如此简单：
 * 就是找最大对称长度的前缀后缀，然后整体右移一位，初值赋为-1
 * (当然，你也可以直接计算某个字符对应的next值，就是看这个字符之前的字符串
 * 中有多大长度的相同前缀后缀）。
 *
 * 对于给定的模式串 abcabx
 * +----------+----+---+---+---+---+---+
 * |    j     | 0  | 1 | 2 | 3 | 4 | 5 |
 * +----------+----+---+---+---+---+---+
 * | 模式串T  | a  | b | c | a | b | x |
 * +----------+----+---+---+---+---+---+
 * | 最大长度 | 0  | 0 | 0 | 1 | 2 | 0 |
 * +----------+----+---+---+---+---+---+
 * | next[j]  | -1 | 0 | 0 | 0 | 1 | 2 |
 * +----------+----+---+---+---+---+---+
 *
 * 根据最大长度表求出了next 数组后，从而有
 * 失配时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值
 *
 * 而后，你会发现，无论是基于"最大长度表"的匹配，还是基于next 数组的匹配，
 * 两者得出来的向右移动的位数是一样的。为什么呢？因为：
 *
 *  > 根据《最大长度表》，失配时，
 *      模式串向右移动的位数 = 已经匹配的字符数 - 失配字符的上一位字符的最大长度值
 *  > 而根据《next 数组》，失配时，
 *      模式串向右移动的位数 = 失配字符的位置 - 失配字符对应的next 值
 *
 * 其中，从0开始计数时，失配字符的位置 = 已经匹配的字符数（失配字符不计数），
 * 而失配字符对应的next 值 = 失配字符的上一位字符的最大长度值，
 * 两相比较，结果必然完全一致。
 * 所以，你可以把《最大长度表》看做是next 数组的雏形，甚至就把它当做next 数组
 * 也是可以的，区别不过是怎么用的问题。
 *
 *
 * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 *
 * 然后其实下标从1开始或者下标从0开始的next数组效果都是一样的
 *
 * +---------+---+---+---+---+---+---+
 * |    j    | 1 | 2 | 3 | 4 | 5 | 6 |
 * +---------+---+---+---+---+---+---+
 * | 模式串T | a | b | c | a | b | x |
 * +---------+---+---+---+---+---+---+
 * | next[j] | 0 | 1 | 1 | 1 | 2 | 3 |
 * +---------+---+---+---+---+---+---+
 *
 * +---------+----+---+---+---+---+---+
 * |    j    | 0  | 1 | 2 | 3 | 4 | 5 |
 * +---------+----+---+---+---+---+---+
 * | 模式串T | a  | b | c | a | b | x |
 * +---------+----+---+---+---+---+---+
 * | next[j] | -1 | 0 | 0 | 0 | 1 | 2 |
 * +---------+----+---+---+---+---+---+
 *
 * 比如x字符失配，那么向右移动的位数 = 失配字符的位置 - 失配字符对应的next 值，
 * 所以下标从1开始的右移位数 = 6 - 3 = 3，
 *     下标从0开始的右移位数 = 5 - 2 = 3。
 *
 * 一般代码的下标都是从0开始的，考试基本都是下标从1开始的，注意一下即可。
 */

/*
 * 下标从0开始的next数组
 * 若模式串的长度为m，则时间复杂度为O(m)
 */
void get_next(char *p, int next[])
{
    int i, k;

    next[0] = -1;
    i = 0;
    k = -1;
    while (p[i] != '\0') {
        if (k == -1 || p[i] == p[k]) {
            ++i;
            ++k;
            next[i] = k;
        } else {
            k = next[k];
        }
    }
}


/*
 * 改进版求next值
 *
 * +----------+----+---+---+----+---+---+
 * |    j     | 0  | 1 | 2 | 3  | 4 | 5 |
 * +----------+----+---+---+----+---+---+
 * | 模式串p  | a  | b | c | a  | b | x |
 * +----------+----+---+---+----+---+---+
 * | 最大长度 | 0  | 0 | 0 | 1  | 2 | 0 |
 * +----------+----+---+---+----+---+---+
 * | next[j]  | -1 | 0 | 0 | 0  | 1 | 2 |
 * +----------+----+---+---+----+---+---+
 * | nextval  | -1 | 0 | 0 | -1 | 0 | 2 |
 * +----------+----+---+---+----+---+---+ 
 *
 * 如果模式串的后缀跟前缀相同，那么它们的next值也是相同的。
 *
 * 推导过程：(p[j] 不能等于 p{next[j]}, 否则 next[j] = next{next[j]})
 * 当j=0时，初值不变，nextval[0] = -1
 * 当j=1时，p[1] = b, p{next[1]} = a, 两者不相等，所以 nextval[1] = next[1] = 0
 * 当j=2时，p[2] = c, p{next[2]} = a, 两者不相等，所以 nextval[2] = next[2] = 0
 * 当j=3时，p[3] = a, p{next[3]} = a, 两者相等，所以 nextval[3] = next{next[3]} = -1
 * 当j=4时，p[4] = b, p{next[4]} = b, 两者相等，所以 nextval[4] = next{next[4]} = 0
 * 当j=5时，p[5] = x, p{next[5]} = c, 两者不相等，所以 nextval[5] = next[5] = 2
 *
 */
void get_nextval(char *p, int nextval[])
{
    int i, k;

    nextval[0] = -1;
    i = 0;
    k = -1;
    while (p[i] != '\0') {
        if (k == -1 || p[i] == p[k]) {
            ++i;
            ++k;
            if (p[i] != p[k]) // 若当前字符和前缀字符不同
                nextval[i] = k;
            else
                nextval[i] = nextval[k];
        } else {
            k = nextval[k];
        }
    }
}


/*
 * KMP算法流程
 * 假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置
 * > 如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++，
 *   继续匹配下一个字符；
 * > 如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]。
 *   此举意味着失配时，模式串P相对于文本串S向右移动了j - next [j] 位。
 *   换言之，当匹配失败时，模式串向右移动的位数为：
 *   失配字符所在位置 - 失配字符对应的next 值，
 *   即移动的实际位数为：j - next[j]，且此值大于等于1。
 *
 * 此也意味着在某个字符失配时，该字符对应的next 值会告诉你下一步匹配中，
 * 模式串应该跳到哪个位置（跳到next [j] 的位置）。如果next [j] 等于0或-1，
 * 则跳到模式串的开头字符，若next [j] = k 且 k > 0，代表下次匹配跳到j 之前
 * 的某个字符，而不是跳到开头，且具体跳过了k 个字符。
 *
 * 参考 https://blog.csdn.net/v_july_v/article/details/7041827
 *
 * 时间复杂度为O(n+m)。n，m分别是主串和模式串的长度。
 */
int str_index_kmp(char *s, char *p)
{
    if (s == NULL || p == NULL)
        return -1;

    int slen = strlen(s);
    int plen = strlen(p);

    if (slen <= 0 || plen <= 0)
        return -1;


    int next[32];
    get_nextval(p, next);
    //int n;
    //for (n = 0; n < plen; ++n)
    //    printf("next[%d] = %d\n", n, next[n]);


    int i = 0;
    int j = 0;
    while (i < slen && j < plen) {
        if (j == -1 || s[i] == p[j]) {
            ++i;
            ++j;
        } else {
            j = next[j];
        }
    }

    if (j == plen)
        return i - j;
    else
        return -1;
}


int main()
{
    char *s = "bbc abcab zyacccabcabxxxaa";
    char *t = "abcabx";

    int i = str_index_kmp(s, t);
    printf("i=[%d]\n", i);


    return 0;
}
